class Solution {
public:
    int Max(vector<int>& nums,int start,int end){
      int len = end - start;
      if(len == 1) return max(nums[start],nums[end]);
      int dp[end+1][2];
      dp[start][0] = 0;
      dp[start][1] = nums[start];
      dp[start+1][0] = nums[start];
      dp[start+1][1] = nums[start+1];

      for(int i = start+2; i <= end;i++){
        dp[i][0] = max(dp[i-1][1],dp[i-2][1]);
        dp[i][1] = dp[i-1][0]+nums[i];
      }
      return max(dp[end][0],dp[end][1]);
    }
    int rob(vector<int>& nums) {
      int len = nums.size();
      if(len==1) return nums[0];
      if(len==2) return max(nums[0],nums[1]);
      return max(Max(nums,0,len-2),Max(nums,1,len-1));
    }
};
